
/**
 * 克鲁斯卡尔算法
 * 思想：将所有边按边权从小到大排序，然后从头开始遍历
 * 将选中的边加入到并查集中，判断是否产生了环，如果没有产生，那么就选中
 * 否则跳过此边
 */

#include<stdio.h>
#include<stdlib.h>
#define MAX_VEX 10
#define INF 65535
// #define DEBUG


typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType *vertexs;//使用指针是方便初始化
    EdgeType **edges;//邻接矩阵
    int numVertexs,numEdges;//顶点数和边数
}Graph;

/**
 * 边类型，这个是用来给边排序的，后面会生成一个Edge的数组
 */
typedef struct Edge{
    EdgeType edgeData;
    int headVertex,tailVertex;
}Edge;

void initGraph(Graph *g){
    //初始化顶点数组
    g->vertexs=(VertexType*) malloc(MAX_VEX*sizeof(VertexType));
    //初始化邻接矩阵
    int i,j;
    g->edges=(EdgeType**)malloc(MAX_VEX*sizeof(EdgeType *));
    for(int i=0;i<MAX_VEX;i++){
        g->edges[i]=(EdgeType*)malloc(MAX_VEX*sizeof(EdgeType));
        for(int j=0;j<MAX_VEX;j++){
            if(i==j){
                g->edges[i][j]=0;//到自己的距离是0
            }else{
                g->edges[i][j]=INF;//到其他顶点的距离为无穷大
            }
        }
    }
    //初始话顶点和边的数量
    g->numVertexs=0;
    g->numEdges=0;
    printf("图初始化完毕...\n");
}

void createGraph(Graph *g){
    int vertex_num=6;
    int edge_num=10;
    char vertex[]={'a','b','c','d','e','f'};    
    int matrix[MAX_VEX][MAX_VEX]={
        {0,6,1,5,0,0},
        {6,0,5,0,3,0},
        {1,5,0,5,6,4},
        {5,0,5,0,0,2},
        {0,3,6,0,0,6},
        {0,0,4,2,6,0},
    };
    g->numVertexs=vertex_num;
    g->numEdges=edge_num;
    for(int i=0;i<vertex_num;i++){
        g->vertexs[i]=vertex[i];
        for(int j=0;j<vertex_num;j++){
            g->edges[i][j]=matrix[i][j];
            g->edges[j][i]=matrix[j][i];
        }
    }
    //将上面的数据赋值给graph
    printf("图创建完毕...\n");
}

/**
 * 比较两个边
 * @param a 边1
 * @param b 边2
 * @return 0相等，大于1则边1权值更大，小于1则边2权值更大
 */
int cmp(const void* a,const void*b){
    Edge*e1=(Edge*)a;
    Edge*e2=(Edge*)b;
    return e1->edgeData - e2->edgeData;
}

/**
 * kruskal的实现
 * 
 */
void kruskal(Graph g){
    int i,j,k=0;
    //辅助边数组
    Edge* edge;
    edge=(Edge*)malloc(MAX_VEX*sizeof(Edge));
    //获取所有边，放到edge数组中,对于无向图，只需要遍历主对角线一侧即可
    for(i=1;i<MAX_VEX;i++){
        for(j=0;j<i;j++){//主对角线下侧
            if(g.edges[i][j]!=0&&g.edges[i][j]!=INF){//这句有bug
                edge[k].edgeData=g.edges[i][j];
                edge[k].headVertex=i;
                edge[k].tailVertex=j;
                k++;
            }
        }
    }
    //对edge数组排序,这个和c++里面的sort类似，最后一个参数是排序的规则
    qsort(edge,g.numEdges,sizeof(Edge),cmp);
    #ifdef DEBUG
    for(i=0;i<g.numEdges;i++){
        j=edge[i].headVertex;
        k=edge[i].tailVertex;
        printf("%c----%d----%c\n",g.vertexs[j],edge[i].edgeData,g.vertexs[k]);
    }
    #endif
    //并查集，判断是否有环
    int *vexset;
    vexset=(int*)malloc(g.numVertexs*sizeof(int));
    //初始化并查集，每个节点都单独成树根，下标是节点，值是父节点
    for(i=0;i<g.numVertexs;i++){
        vexset[i]=i;//这里等于-1也行吧，就是不指向任何节点,那么后面的判断就要变了
    }

    //选择最小的边
    int v1,v2,head,tail;
    //在视频中，用edgeNumber记录已经加入的边数，到顶点减一的时候停止，这里并没有那么做，而是把所有边遍历一遍
    for(i=0;i<g.numEdges;i++){ 
        v1=edge[i].headVertex;
        v2=edge[i].tailVertex;
        head=vexset[v1];
        tail=vexset[v2];
        //如果头尾不再一个集合中，就合并成一个集合,并输出连接后的结果
        //如果二者相等，说明在同一个集合里面，在加一条边的话，必定成换
        //注意，这里直接比较head和tail下标的元素，前提是，这个并查集，每个顶点所属集合（下标对应的值）都是数的最顶上的根
        //保证了集合标记的唯一性，不用像tree文件夹里面的那个并查集使用while循环找根
        if(vexset[head]!=vexset[tail]){
            printf("%c----(%d)----%c\n",g.vertexs[head],g.edges[head][tail],g.vertexs[tail]);
            //合并头尾到一个集合中
            for(j=0;j<g.numVertexs;j++){
                if(vexset[j]==tail) vexset[j]=head;
            }
        }
    }
}


int main(void){
    Graph g;
    initGraph(&g);
    createGraph(&g);
    kruskal(g);
    return 0;
}